package com.ying.tree;

import java.util.*;

class Node {
    int id;
    int parentId;
    int originalOrder;
    int newOrder;
    String name;
    List<Node> children;

    public Node(int id, int parentId, int originalOrder, String  name) {
        this.id = id;
        this.parentId = parentId;
        this.originalOrder = originalOrder;
        this.name = name;
        this.children = new ArrayList<>();
    }

    // Getters and setters
    public int getId() { return id; }
    public int getParentId() { return parentId; }
    public int getOriginalOrder() { return originalOrder; }
    public int getNewOrder() { return newOrder; }
    public String  getName() { return name; }

    public List<Node> getChildren() { return children; }
}

public class DepartmentTreeSorter {

    public static void main(String[] args) {
        System.out.println("开始");
        // 创建示例节点
        List<Node> nodes = new ArrayList<>();
        nodes.add(new Node(1, 0, 0, "浦银理财")); // 根节点
        nodes.add(new Node(2, 1, 17 , "----金融科技部")); // A节点
        nodes.add(new Node(3, 2, 2,"------CISP")); // B节点
        nodes.add(new Node(4, 2, 99,"------统一工作台")); // B节点
        nodes.add(new Node(11, 4, 3,"--------统一分公司1")); // C节点
        nodes.add(new Node(12, 4, 3,"--------统一分公司2")); // C节点
        nodes.add(new Node(8, 2, 223,"------复仇者")); // B节点
        nodes.add(new Node(21, 8, 3,"--------复仇者分公司1")); // C节点
        nodes.add(new Node(22, 8, 3,"--------复仇者分公司2")); // C节点
        nodes.add(new Node(27, 22, 3,"----------sub复仇者分公司")); // C节点
        nodes.add(new Node(5, 1, 19,"----成都分公司")); // C节点
        nodes.add(new Node(6, 5, 6,"------绵阳分公司")); // C节点
        nodes.add(new Node(7, 6, 3,"--------永祥分公司")); // C节点

        // 构建树结构
        Node root = buildTree(nodes);
        
        // 分配新排序
        assignNewOrder(root);
        
        // 打印结果
        printTree(root);
    }

    // 构建树结构
    private static Node buildTree(List<Node> nodes) {
        System.out.println("构建树结构");
        Map<Integer, Node> nodeMap = new HashMap<>();
        for (Node node : nodes) {
            nodeMap.put(node.getId(), node);
        }
        Node root = null;
        for (Node node : nodes) {
            if (node.getId() == 1) { // 假设根节点的parentId为0
                root = node;
            } else {
                Node parent = nodeMap.get(node.getParentId());
                if (parent != null) {
                    parent.getChildren().add(node);
                }
            }
        }
        return root;
    }

    // 分配新排序（BFS实现）
    private static void assignNewOrder(Node root) {
        System.out.println("分配新排序");
        if (root == null) return;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        root.newOrder = 100;
        int currentOrder = 100;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            // 获取子节点并按原排序排序
            List<Node> sortedChildren = new ArrayList<>(node.getChildren());
            sortedChildren.sort(Comparator.comparingInt(Node::getOriginalOrder));
            // 为子节点分配新排序并加入队列
            for (Node child : sortedChildren) {
                currentOrder++;
                child.newOrder = currentOrder;
                queue.add(child);
            }
        }
    }

    // 打印树结构
    private static void printTree(Node node) {
        System.out.println("打印树结构");
        List<Node> list = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            list.add(current);
            System.out.printf("节点ID: %d, 名称: %s,  原排序: %d, 新排序: %d%n",
                    current.getId(), current.getName() , current.getOriginalOrder(), current.getNewOrder());
            for (Node child : current.getChildren()) {
                queue.add(child);
            }
        }

        list.sort(Comparator.comparingInt(Node::getNewOrder));

        for (Node node1 : list) {
            System.out.println(node1.getId()+" "+ node1.getName()+" "+ node1.getNewOrder() );
            
        }
    }
}